package com.nowcoder.Offer.Tree;

import org.junit.Test;

import java.util.ArrayList;

/**
 * 二叉树和为某一值的路径
 */
public class FindPathInTree {

    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<>();
        dfs(path,root,target);
        return ans;
    }

    public void dfs(ArrayList<Integer> path, TreeNode curNode, int target){
        if(curNode == null) return;
        target -= curNode.val;

        path.add(curNode.val);

        if(target == 0 && curNode.left == null && curNode.right == null){
            ans.add(new ArrayList<>(path));
        }else{
            dfs(path,curNode.left,target);
            dfs(path,curNode.right,target);
        }

        path.remove(path.size()-1);
    }

    @Test
    public void test(){

    }
}
